class Solution(object):
    def __init__(self):
        self.res = 0

    def movingCount(self, k, rows, cols):
        if rows == 0 or cols == 0:
            return 0
        st = [[0] * cols for _ in range(rows)]
        dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]

        def check(i, j):
            ans = 0
            while i:
                ans += i % 10
                i = i // 10
            while j:
                ans += j % 10
                j = j // 10
            return ans

        def dfs(x, y):
            self.res += 1
            st[x][y] = 1
            for i in range(4):
                nx, ny = x + dx[i], y + dy[i]
                if nx >= 0 and ny >= 0 and nx < rows and ny < cols and st[nx][ny] == 0 and check(nx, ny) <= k:
                    st[nx][ny] = 1
                    dfs(nx, ny)

        dfs(0, 0)
        return self.res